//
// Description: 19. 删除链表的倒数第 N 个结点
// Created by Loading on 2022/4/3.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

ListNode* removeNthFromEnd(ListNode* head, int n) {
    auto hair = new ListNode(0);
    hair->next = head;
    auto pre = hair;
    auto fast = hair;
    // 快慢指针
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }
    while (fast->next) {
        fast = fast->next;
        pre = pre->next;
    }
    pre->next = pre->next->next;

    auto res = hair->next;
    delete hair;
    return res;
}

int main() {
    vector<int> nums{1,2,3,4,5};
    auto head = generateListNode(nums);
    int n = 2;
    auto res = removeNthFromEnd(head, n);
    cout << printfListNode(res) << endl;

    return 0;
}